{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Where Will the Ball Fall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #array #dynamic-programming #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #数组 #动态规划 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findBall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #球会落何处"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>用一个大小为 <code>m x n</code> 的二维网格 <code>grid</code> 表示一个箱子。你有 <code>n</code> 颗球。箱子的顶部和底部都是开着的。</p>\n",
    "\n",
    "<p>箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将球导向右侧的挡板跨过左上角和右下角，在网格中用 <code>1</code> 表示。</li>\n",
    "\t<li>将球导向左侧的挡板跨过右上角和左下角，在网格中用 <code>-1</code> 表示。</li>\n",
    "</ul>\n",
    "\n",
    "<p>在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 \"V\" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。</p>\n",
    "\n",
    "<p>返回一个大小为 <code>n</code> 的数组 <code>answer</code> ，其中 <code>answer[i]</code> 是球放在顶部的第 <code>i</code> 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/12/26/ball.jpg\" style=\"width: 500px; height: 385px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]\n",
    "<strong>输出：</strong>[1,-1,-1,-1,-1]\n",
    "<strong>解释：</strong>示例如图：\n",
    "b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。\n",
    "b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 \"V\" 形里。\n",
    "b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 \"V\" 形里。\n",
    "b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 \"V\" 形里。\n",
    "b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 \"V\" 形里。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[-1]]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>球被卡在箱子左侧边上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]\n",
    "<strong>输出：</strong>[0,1,2,3,4,-1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 为 <code>1</code> 或 <code>-1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [where-will-the-ball-fall](https://leetcode.cn/problems/where-will-the-ball-fall/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [where-will-the-ball-fall](https://leetcode.cn/problems/where-will-the-ball-fall/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]', '[[-1]]', '[[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i]== -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j +=direction\n",
    "\n",
    "                if j<0 or j ==n or row[j]!=direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n        \n",
    "        for i in range(n):\n",
    "            j = i # 当前 i 号球所在的位置\n",
    "            for row in grid: \n",
    "                direction = row[j] # 方问\n",
    "                j += direction # 当前 i 号球滚动后的位置\n",
    "                # 已经出界或挡板方向相反\n",
    "                if j < 0 or j == n or row[j] != direction: break\n",
    "            else: ans[i] = j\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        res = [-1] * n         \n",
    "        for i in range(n):\n",
    "        \t# 一个一个处理\n",
    "            col = i # 先保存当前球 i 的位置 \n",
    "            for row in grid:\n",
    "                direction = row[col] # 方向\n",
    "                col += direction # 滚动后的位置\n",
    "                # 出界或前后方向不同，终止内循环。\n",
    "                if col < 0 or col == n or row[col] != direction: break\n",
    "            else: res[i] = col\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res  = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j += direction\n",
    "\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "      m, n = len(grid), len(grid[0])\n",
    "      dp = {i:i for i in range(n)}\n",
    "      for i in range(m):\n",
    "        for k in list(dp.keys()):\n",
    "          if grid[i][dp[k]] == 1:\n",
    "             if dp[k] == n - 1 or grid[i][dp[k] + 1] == -1:\n",
    "                dp.pop(k)\n",
    "             else:\n",
    "                dp[k] += 1\n",
    "          else:\n",
    "            if not dp[k] or grid[i][dp[k] - 1] == 1:\n",
    "               dp.pop(k)\n",
    "            else:\n",
    "                dp[k] -= 1\n",
    "      return [dp[i] if i in dp else -1 for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = {i:i for i in range(n)}\n",
    "        for i in range(m):\n",
    "            for k in list(dp.keys()):\n",
    "                if grid[i][dp[k]] == 1:\n",
    "                    if dp[k] == n - 1 or grid[i][dp[k] + 1] == -1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] += 1\n",
    "                else:\n",
    "                    if not dp[k] or grid[i][dp[k] - 1] == 1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] -= 1\n",
    "        return [dp[i] if i in dp else -1 for i in range(n)] \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        '''\n",
    "        根据题意进行模拟，逐列统计每个Column中小球的去向，主要根据其目前所在位置的挡板判断其在下一行的去向，并处理边界条件(遇到左右挡板或是\"V\"型图案)，直至其到达最后一行。\n",
    "        '''\n",
    "        r = len(grid)           #Row\n",
    "        c = len(grid[0])        #Column\n",
    "        ans = []\n",
    "        for i in range(c):      #逐列统计每个Column中小球的去向\n",
    "            prev = i\n",
    "            for j in range(r):\n",
    "                now = prev + grid[j][prev]       #滑向哪一列挡板\n",
    "                if now == -1 or now == c or grid[j][now] != grid[j][prev]:      #处理边界条件，遇到左右挡板，或是滑向格的挡板方向与原来格的挡板方向不一致，则遇到\"V\"型图案。\n",
    "                    ans.append(-1)  #球卡在盒子里\n",
    "                    break\n",
    "                prev = now          #没遇到边界条件，则正常滑向该格挡板\n",
    "                if j == r - 1:      #到达最后一行，并且没有遇到边界条件\n",
    "                    ans.append(now) #球从第now列掉出来\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = {i:i for i in range(n)}\n",
    "        for i in range(m):\n",
    "            for k in list(dp.keys()):\n",
    "                if grid[i][dp[k]] == 1:\n",
    "                    if dp[k] == n - 1 or grid[i][dp[k] + 1] == -1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] += 1\n",
    "                else:\n",
    "                    if not dp[k] or grid[i][dp[k] - 1] == 1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] -= 1\n",
    "        return [dp[i] if i in dp else -1 for i in range(n)] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        a=len(grid[0])\n",
    "        b=[-1]*a\n",
    "        for i in range(a):\n",
    "            c=i\n",
    "            for j in grid:\n",
    "                fx=j[c] #方向\n",
    "                c+=fx\n",
    "                if c<0 or c==a or fx!=j[c]:\n",
    "                    break\n",
    "            else:\n",
    "                b[i]=c\n",
    "        return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i]  == -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j += direction\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                ans[j] = col\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "                res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j += direction\n",
    "\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i]== -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j +=direction\n",
    "\n",
    "                if j<0 or j ==n or row[j]!=direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = [0] * n\n",
    "        for idx in range(n):\n",
    "            i, j = 0, idx\n",
    "            is_su = True\n",
    "            while i < m:\n",
    "                if grid[i][j] == 1:\n",
    "                    if j + 1 >= n or grid[i][j + 1] == -1:\n",
    "                        is_su = False\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    if j - 1 < 0 or grid[i][j - 1] == 1:\n",
    "                        is_su = False\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                    continue\n",
    "            res[idx] = j if is_su is True else -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                ans[j] = col\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res =[]\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i] \n",
    "                direction = row[j]\n",
    "                j += direction\n",
    "\n",
    "                if j < 0 or j==n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid: # 提取行\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i] # 当前 i 号球所在的位置\n",
    "                direction = row[j] # 方问\n",
    "                j += direction # 当前 i 号球滚动后的位置\n",
    "                # 已经出界或挡板方向相反\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        def judge(x,row,col,grid):\n",
    "            r = 0\n",
    "            while r < row:\n",
    "                temp = grid[r][x]\n",
    "                if x + temp <0 or x + temp == col:\n",
    "                    return -1\n",
    "                if grid[r][x] != grid[r][x+temp]:\n",
    "                    return -1\n",
    "                x += temp\n",
    "                r += 1\n",
    "            return x\n",
    "        return [judge(i,row,col,grid) for i in range(col)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        if grid == []:\n",
    "            return []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0]) \n",
    "        answer = [i for i in range(n)]\n",
    "       # up = [True for i in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if answer[j] != -1:\n",
    "                    if grid[i][answer[j]] == 1:\n",
    "                        answer[j] = -1 if (answer[j] == n-1 or grid[i][answer[j] + 1] == -1) else answer[j] + 1\n",
    "                    else:\n",
    "                        answer[j] = -1 if (answer[j] == 0 or grid[i][answer[j] - 1] == 1) else answer[j] - 1\n",
    "\n",
    "        return answer       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n=len(grid[0])\n",
    "        output=[-1]*n\n",
    "        for j in range(n):\n",
    "            col=j\n",
    "            arrive=True\n",
    "            for row in grid:\n",
    "                dir=row[col]\n",
    "                col+=dir\n",
    "                if col<0 or col==n or dir!=row[col]:\n",
    "                    arrive=False\n",
    "                    break\n",
    "            if arrive:\n",
    "                output[j]=col\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        balls = list(range(n))\n",
    "        for c in range(n):\n",
    "            b = c\n",
    "            for r in range(m):\n",
    "                if b < n-1 and grid[r][b] == 1 and grid[r][b+1] == -1:\n",
    "                    balls[c] = -1\n",
    "                    break\n",
    "                elif grid[r][b] == -1 and grid[r][b-1] == 1:\n",
    "                    balls[c] = -1\n",
    "                    break\n",
    "                balls[c] += grid[r][b]\n",
    "                b += grid[r][b]\n",
    "                if balls[c] == -1 or balls[c] == n:\n",
    "                    balls[c] = -1\n",
    "                    break\n",
    "        return(balls)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        result = [-1]*n\n",
    "        for j in range(n):\n",
    "            col = j\n",
    "            for row in grid:\n",
    "                obs = row[col]\n",
    "                col = col + obs\n",
    "                if col < 0 or col > n-1 or row[col] != obs:\n",
    "                    break\n",
    "            else: result[j] = col\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [-1]*n\n",
    "        def check(i,j):#i,j表示可以到达这个格子的正上方，返回下一个格子或者Fasle表示被卡住了\n",
    "            if j<n-1 and grid[i][j]==grid[i][j+1]==1:\n",
    "                return [i+1,j+1]\n",
    "            elif 0<j<n and grid[i][j]==grid[i][j-1]==-1:\n",
    "                return [i+1,j-1]\n",
    "            else:\n",
    "                return False,-1\n",
    "        for i in range(n):\n",
    "            #遍历每一列\n",
    "            beginx,beginy=0,i\n",
    "            flag = False\n",
    "            for j in range(m):\n",
    "                beginx,beginy = check(beginx,beginy)\n",
    "                if beginy==-1:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                res[i]=beginy\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 模拟\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = []\n",
    "\n",
    "        def getVal(x):\n",
    "            nonlocal m, n, grid\n",
    "            r, c = 0, x\n",
    "            while r < m:\n",
    "                nc = c + grid[r][c]     # 计算小球运动的下一列\n",
    "                if nc < 0 or nc >= n:   # 出界\n",
    "                    return -1\n",
    "                if grid[r][c] != grid[r][nc]:   # 下一列的朝向与当前列不同\n",
    "                    return -1\n",
    "                r, c = r + 1, nc    # 更新小球位置\n",
    "            \n",
    "            return c\n",
    "        \n",
    "        for i in range(n):\n",
    "            ans.append(getVal(i))\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        # 记录每个球的下标\n",
    "        res = [i for i in range(n)]\n",
    "        for row in grid: # 提取行\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i] # 当前 i 号球所在的位置\n",
    "                direction = row[j] # 方问\n",
    "                j += direction # 当前 i 号球滚动后的位置\n",
    "                # 已经出界或挡板方向相反\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                ans[j] = col\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        height = len(grid)\n",
    "        width = len(grid[0])\n",
    "        def getRes(y):\n",
    "            level = 0\n",
    "            while level < height:\n",
    "                ny = y + grid[level][y]\n",
    "                if ny < 0 or ny >= width: return -1\n",
    "                if grid[level][y] + grid[level][ny] == 0: return -1\n",
    "                y = ny\n",
    "                level+=1\n",
    "            return y\n",
    "        res = []\n",
    "        for i in range(width):res.append(getRes(i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n=len(grid[0])\n",
    "        output=[-1]*n\n",
    "        for j in range(n):\n",
    "            col=j\n",
    "            arrive=True\n",
    "            for row in grid:\n",
    "                dir=row[col]\n",
    "                col+=dir\n",
    "                if col==-1 or col==n or row[col]!=dir:\n",
    "                    arrive=False\n",
    "                    break\n",
    "            if arrive:\n",
    "                output[j]=col\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                ans[j] = col\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = [0] * n\n",
    "        for idx in range(n):\n",
    "            i, j = 0, idx\n",
    "            is_su = True\n",
    "            while i < m:\n",
    "                if grid[i][j] == 1:\n",
    "                    if j + 1 >= n or grid[i][j + 1] == -1:\n",
    "                        is_su = False\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    if j - 1 < 0 or grid[i][j - 1] == 1:\n",
    "                        is_su = False\n",
    "                        break\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                    continue\n",
    "            res[idx] = j if is_su is True else -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid:\n",
    "            for i in range(n):\n",
    "                if res[i]== -1: continue\n",
    "                j = res[i]\n",
    "                direction = row[j]\n",
    "                j +=direction\n",
    "\n",
    "                if j<0 or j ==n or row[j]!=direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                    ans[j] = col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row in grid: # 提取行\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i] # 当前 i 号球所在的位置\n",
    "                direction = row[j] # 方问\n",
    "                j += direction # 当前 i 号球滚动后的位置\n",
    "                # 已经出界或挡板方向相反\n",
    "                if j < 0 or j == n or row[j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        res = [i for i in range(len(grid[0]))]\n",
    "        for j in range(len(grid)):\n",
    "            i = 0\n",
    "            while i < len(grid[0]):\n",
    "                m = res[i]\n",
    "                if m >= 0:\n",
    "                    if grid[j][m] == -1:\n",
    "                        if m == 0 or grid[j][m-1] == 1:\n",
    "                            res[i] = -1\n",
    "                        else:\n",
    "                            res[i] -= 1\n",
    "                    else:\n",
    "                        if m == len(grid[0]) - 1 or grid[j][m+1] == -1:\n",
    "                            res[i] = -1\n",
    "                        else:\n",
    "                            res[i] += 1\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = {i: i for i in range(n)}\n",
    "        for i in range(m):\n",
    "            for k in list(dp.keys()):\n",
    "                if grid[i][dp[k]] == 1:\n",
    "                    if dp[k] == n - 1 or grid[i][dp[k] + 1] == -1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] += 1\n",
    "                else:\n",
    "                    if dp[k] == 0 or grid[i][dp[k] - 1] == 1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] -= 1\n",
    "        return [dp[i] if i in dp else -1 for i in range(n)] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n=len(grid[0])\n",
    "        ans=[-1]*n\n",
    "        for j in range(n):\n",
    "            col=j\n",
    "            for row in grid:\n",
    "                dir =row[col]\n",
    "                col+=dir\n",
    "                if col<0 or col==n or row[col]!=dir:\n",
    "                    break\n",
    "            else:\n",
    "                ans[j]=col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n=len(grid[0])\n",
    "        output=[-1]*n\n",
    "        for j in range(n):\n",
    "            col=j\n",
    "            arrive=True\n",
    "            for row in grid:\n",
    "                dir=row[col]\n",
    "                col+=dir\n",
    "                if col==-1 or col==n or dir!=row[col]:\n",
    "                    arrive=False\n",
    "                    break\n",
    "            if arrive:\n",
    "                output[j]=col\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "         n = len(grid[0])\n",
    "         ans = [-1] * n\n",
    "         for j in range(n):\n",
    "            col = j  \n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  \n",
    "                if col < 0 or col == n or row[col] != dir:  \n",
    "                    break\n",
    "            else: \n",
    "                ans[j] = col\n",
    "         return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[-1]*n for _ in range(m+1)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = j\n",
    "        for i in range(0, m):\n",
    "            for j in range(n):\n",
    "                tmp = dp[i][j]\n",
    "                if tmp == -1:\n",
    "                    continue\n",
    "                elif tmp < n-1 and grid[i][tmp] == 1 and grid[i][tmp+1] == 1:\n",
    "                    dp[i+1][j] = dp[i][j]+1\n",
    "                elif tmp > 0 and grid[i][tmp-1] == -1 and grid[i][tmp] == -1:\n",
    "                    dp[i+1][j] = dp[i][j]-1\n",
    "                else:\n",
    "                    dp[i+1][j] = -1\n",
    "        return dp[m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [-1]*n\n",
    "        def check(i,j):#i,j表示可以到达这个格子的正上方，返回下一个格子或者Fasle表示被卡住了\n",
    "            if j<n-1 and grid[i][j]==grid[i][j+1]==1:\n",
    "                return [i+1,j+1]\n",
    "            elif 0<j<n and grid[i][j]==grid[i][j-1]==-1:\n",
    "                return [i+1,j-1]\n",
    "            else:\n",
    "                return False\n",
    "        for i in range(n):\n",
    "            #遍历每一列\n",
    "            beginx,beginy=0,i\n",
    "            flag = False\n",
    "            for j in range(m):\n",
    "                if check(beginx,beginy)==False:\n",
    "                    flag = True\n",
    "                    break\n",
    "                else:\n",
    "                    beginx,beginy = check(beginx,beginy)\n",
    "            if not flag:\n",
    "                res[i]=beginy\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = [0]*n\n",
    "        for j in range(n):\n",
    "            cur = j\n",
    "            for i in range(m):\n",
    "                if grid[i][cur]==-1:\n",
    "                    if cur==0 or grid[i][cur-1]==1:\n",
    "                        res[j]=-1\n",
    "                        break\n",
    "                    else:\n",
    "                        cur-=1\n",
    "                else:\n",
    "                    if cur==n-1 or grid[i][cur+1]==-1:\n",
    "                        res[j]=-1\n",
    "                        break\n",
    "                    else:\n",
    "                        cur+=1\n",
    "                if i==m-1:\n",
    "                    res[j]=cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            col = i\n",
    "            for row in grid:\n",
    "                cur = row[col]\n",
    "                col += cur\n",
    "                if col < 0 or col == n or row[col] != cur:\n",
    "                    break\n",
    "            else:\n",
    "                ans[i] = col\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = {i:i for i in range(n)}\n",
    "        for i in range(m):\n",
    "            for k in list(dp.keys()):\n",
    "                if grid[i][dp[k]] == 1:\n",
    "                    if dp[k] == n - 1 or grid[i][dp[k] + 1] == -1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] += 1\n",
    "                else:\n",
    "                    if not dp[k] or grid[i][dp[k] - 1] == 1:\n",
    "                        dp.pop(k)\n",
    "                    else:\n",
    "                        dp[k] -= 1\n",
    "        return [dp[i] if i in dp else -1 for i in range(n)] \n",
    "\n",
    "                \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        res = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j\n",
    "            for row in grid:\n",
    "                tmp = row[col]\n",
    "                col += tmp\n",
    "                if col < 0 or col == n or row[col] != tmp: break\n",
    "            else: res[j] = col\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [-1]*n\n",
    "        for j in range(n):\n",
    "            cur_col = j\n",
    "            for i in range(m):\n",
    "                dir = grid[i][cur_col]\n",
    "                cur_col += dir\n",
    "                if cur_col < 0 or cur_col >= n or grid[i][cur_col] != dir:\n",
    "                    break\n",
    "            else:\n",
    "                ans[j] = cur_col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = []\n",
    "        def getval(index):\n",
    "            row = 0\n",
    "            col = i\n",
    "            while row < m:\n",
    "                if col < 0 or col >= n or (col == n - 1 and grid[row][col] == 1) or (col == 0 and grid[row][col] == -1):\n",
    "                    return -1\n",
    "                    break\n",
    "                if col + 1 <= n - 1 and grid[row][col] == 1 and grid[row][col + 1] == 1:\n",
    "                    row += 1\n",
    "                    col += 1\n",
    "                elif col - 1 >= 0 and grid[row][col] == -1 and grid[row][col - 1] == -1:\n",
    "                    row += 1\n",
    "                    col -= 1\n",
    "                else:\n",
    "                    return -1\n",
    "            return col\n",
    "\n",
    "        for i in range(n):\n",
    "            ans.append(getval(i))\n",
    "\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        Row = len(grid)\n",
    "        Col = len(grid[0])\n",
    "        res = [-1 for _ in range(Col)]\n",
    "        \n",
    "        for c in range(Col):\n",
    "            pos = c\n",
    "            ok = True\n",
    "            for r in range(Row):\n",
    "                #----向左\n",
    "                if grid[r][pos] == -1:\n",
    "                    if 0 <= pos - 1 and grid[r][pos - 1] == -1:\n",
    "                        pos -= 1\n",
    "                    else:\n",
    "                        ok = False\n",
    "                        break\n",
    "                else:\n",
    "                    if pos + 1 < Col and grid[r][pos + 1] == 1:\n",
    "                        pos += 1\n",
    "                    else:\n",
    "                        ok = False\n",
    "                        break\n",
    "\n",
    "            res[c] = pos if ok == True else -1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        # 能通过的条件是两列都是1 或者 都是-1, 模拟即可\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = [-1]*n\n",
    "\n",
    "        for c in range(n):\n",
    "            cur_col = c\n",
    "            flag = True\n",
    "            for i in range(m):\n",
    "                if grid[i][cur_col]==1:\n",
    "                    if cur_col<n-1 and grid[i][cur_col+1]==1:\n",
    "                        cur_col+=1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    if cur_col>0 and grid[i][cur_col-1]==-1:\n",
    "                        cur_col -= 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                pass\n",
    "            ans[c] = cur_col if flag else -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\r\n",
    "        n = len(grid[0])\r\n",
    "        ans = [-1] * n\r\n",
    "        for j in range(n):\r\n",
    "            col = j\r\n",
    "            for row in range(len(grid)):\r\n",
    "                dir = grid[row][col]\r\n",
    "                col += dir\r\n",
    "                if col <0 or col >= n or grid[row][col] != dir:\r\n",
    "                    ans[j] = -1\r\n",
    "                    break\r\n",
    "                else:\r\n",
    "                    ans[j] = col\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            cur = i\n",
    "            for j in range(m):\n",
    "                nxt = cur+grid[j][cur]\n",
    "                if 0 <= nxt and nxt < n and grid[j][cur] == grid[j][nxt]:\n",
    "                    cur = nxt\n",
    "                else:\n",
    "                    ans.append(-1)\n",
    "                    break\n",
    "            if len(ans) <= i:\n",
    "                ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        ans = [-1]*n\n",
    "\n",
    "        for c in range(n):\n",
    "            cur_col = c\n",
    "            flag = True\n",
    "            for i in range(m):\n",
    "                if grid[i][cur_col]==1:\n",
    "                    if cur_col<n-1 and grid[i][cur_col+1]==1:\n",
    "                        cur_col+=1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    if cur_col>0 and grid[i][cur_col-1]==-1:\n",
    "                        cur_col -= 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                pass\n",
    "            ans[c] = cur_col if flag else -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def get(j):\n",
    "            for i in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    if j + 1 == n or grid[i][j + 1] == -1:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        j = j + 1\n",
    "                else:\n",
    "                    if j - 1 == -1 or grid[i][j - 1] == 1:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        j = j - 1\n",
    "            return j\n",
    "        return [get(j) for j in range(n)]\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j  # 球的初始列\n",
    "            for row in grid:\n",
    "                dir = row[col]\n",
    "                col += dir  # 移动球\n",
    "                if col < 0 or col == n or row[col] != dir:  # 到达侧边或 V 形\n",
    "                    break\n",
    "            else:  # 成功到达底部\n",
    "                ans[j] = col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        di = dict(zip(range(n),range(n)))\n",
    "        for l in grid[::-1]:\n",
    "            new_di = dict()\n",
    "            for x,i in di.items():\n",
    "                if i != 0 and l[i] == l[i-1] == 1: new_di[x] = i-1\n",
    "                elif i != n-1 and l[i] == l[i+1] == -1: new_di[x] = i+1\n",
    "            di = new_di\n",
    "        ans = [-1] * n\n",
    "        for x,i in di.items(): ans[i] = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if n == 1: return [-1]\n",
    "        ans = [i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            k = ans[i]\n",
    "            flag = True\n",
    "            for j in range(m):\n",
    "                if k == 0:\n",
    "                    if grid[j][k] == grid[j][k + 1] == 1:\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                elif 0 < k < n - 1:\n",
    "                    if grid[j][k] == grid[j][k + 1] == 1:\n",
    "                        k += 1\n",
    "                    elif grid[j][k] == grid[j][k - 1] == -1:\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "                else:\n",
    "                    if grid[j][k] == grid[j][k - 1] == -1:\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        flag = False\n",
    "                        break\n",
    "            if flag == False:\n",
    "                ans[i] = -1\n",
    "            else:\n",
    "                ans[i] = k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(len(grid[0])):\n",
    "            pos = [0,i]\n",
    "            go = True\n",
    "            while go:\n",
    "                if pos[0]<=m-1:\n",
    "                    if (grid[pos[0]][pos[1]]==1 and pos[1]+1==n) or (pos[1]+1<n and grid[pos[0]][pos[1]]==1 and grid[pos[0]][pos[1]+1]==-1) or (grid[pos[0]][pos[1]]==-1 and pos[1]==0) or (pos[1]-1>=0 and grid[pos[0]][pos[1]]==-1 and grid[pos[0]][pos[1]-1]==1):\n",
    "                        go = False\n",
    "                        res.append(-1)\n",
    "                    else:\n",
    "                        if grid[pos[0]][pos[1]] == 1:\n",
    "                            pos[0] += 1\n",
    "                            pos[1] += 1\n",
    "                        elif grid[pos[0]][pos[1]] == -1:\n",
    "                            pos[0] += 1\n",
    "                            pos[1] -= 1\n",
    "                else:\n",
    "                    res.append(pos[1])\n",
    "                    go = False\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dp = [[-1]*n for _ in range(m+1)]\n",
    "        for j in range(n):\n",
    "            dp[0][j] = j\n",
    "        for i in range(0, m):\n",
    "            for j in range(n):\n",
    "                tmp = dp[i][j]\n",
    "                if tmp == -1:\n",
    "                    continue\n",
    "                elif tmp < n-1 and grid[i][tmp] == 1 and grid[i][tmp+1] == 1:\n",
    "                    dp[i+1][j] = dp[i][j]+1\n",
    "                elif tmp > 0 and grid[i][tmp-1] == -1 and grid[i][tmp] == -1:\n",
    "                    dp[i+1][j] = dp[i][j]-1\n",
    "                else:\n",
    "                    dp[i+1][j] = -1\n",
    "        return dp[m] \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        direction = [(1, 1), (1, -1)]\n",
    "        direct_enum = -1    # 0表示右 1表示左\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        x = 0\n",
    "        for y in range(n):\n",
    "            x = 0\n",
    "            can_run = 1\n",
    "            while can_run and 0 <= x < len(grid) and 0 <= y < len(grid[0]):\n",
    "                if grid[x][y] == 1:     # 向右\n",
    "                    direct_enum = 0\n",
    "                    if y == n - 1:\n",
    "                        res.append(-1)\n",
    "                        can_run = 0\n",
    "                        break\n",
    "                    if grid[x][y+1] == -1:\n",
    "                        res.append(-1)\n",
    "                        can_run = 0\n",
    "                        break\n",
    "                else:                   # 向左\n",
    "                    direct_enum = 1\n",
    "                    if y == 0:\n",
    "                        res.append(-1)\n",
    "                        can_run = 0\n",
    "                        break\n",
    "                    if grid[x][y-1] == 1:\n",
    "                        res.append(-1)\n",
    "                        can_run = 0\n",
    "                        break\n",
    "                x += direction[direct_enum][0]\n",
    "                y += direction[direct_enum][1]\n",
    "            if can_run:\n",
    "                res.append(y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            res.append(i)\n",
    "\n",
    "        for row  in grid: # 提取行\n",
    "            for i in range(n):\n",
    "                if res[i] == -1: continue\n",
    "                j = res[i] # 当前 i 号球所在位置\n",
    "                direction = row[j] # 方向\n",
    "                j += direction # 当前 i 号球滚动后的位置\n",
    "                # 已经出界或挡板方向相反\n",
    "                if j < 0 or j == n or row [j] != direction: res[i] = -1\n",
    "                else: res[i] = j\n",
    "        return res        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        old_answers = [i for i in range(n)]\n",
    "\n",
    "        \n",
    "        for i in range(m-1,-1,-1):\n",
    "            answers = [n]*n\n",
    "            for j in range(0,n):\n",
    "                if j+grid[i][j] < 0 or j+ grid[i][j] > n-1:\n",
    "                    answers[j] = -1\n",
    "                else:\n",
    "                    answers[j] = old_answers[j+grid[i][j]]\n",
    "            for j in range(0,n-1):\n",
    "                if j+grid[i][j] > j+1 + grid[i][j+1]:\n",
    "                    answers[j] = -1\n",
    "                    answers[j+1] = -1\n",
    "                # elif answers[j]!= -1:\n",
    "                #     answers[j] = old_answers[j+grid[i][j]]\n",
    "                \n",
    "            \n",
    "            old_answers = answers\n",
    "\n",
    "\n",
    "\n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for j in range(n):\n",
    "            col = j\n",
    "            for row in grid:\n",
    "                direction = row[col]\n",
    "                col += direction\n",
    "                if col < 0 or col == n or row[col] != direction:\n",
    "                    break\n",
    "            else:\n",
    "                ans[j] = col\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        ans = [-1] * n\n",
    "        for i in range(n):\n",
    "            res = i\n",
    "            for row in grid:\n",
    "                temp = row[res]\n",
    "                res += temp\n",
    "                if res < 0 or res == n or row[res] != temp:\n",
    "                    break\n",
    "            else:\n",
    "                ans[i] = res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid):\n",
    "\n",
    "        def check(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                if y == n-1:\n",
    "                    return -1\n",
    "                if grid[x][y+1] == -1:\n",
    "                    return -1\n",
    "                y += 1\n",
    "                x += 1\n",
    "                if x < m:\n",
    "                    return check(x, y)\n",
    "                return y\n",
    "            else:\n",
    "                if y == 0:\n",
    "                    return -1\n",
    "                elif grid[x][y-1] == 1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                    x += 1\n",
    "                    if x < m:\n",
    "                        return check(x, y)\n",
    "                    return y\n",
    "        list1 = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(len(grid[0])):\n",
    "            list1.append(check(0, i))\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        def find(x, y,n, m):\n",
    "            if x == n:\n",
    "                return y\n",
    "            if grid[x][y] == 1:\n",
    "                if y+1 < m and grid[x][y+1] == -1:\n",
    "                    return -1\n",
    "                elif y + 1==m :\n",
    "                    return -1\n",
    "                else:\n",
    "                    return find(x+1, y+1,n, m)\n",
    "            elif grid[x][y] == -1:\n",
    "                if y - 1 >= 0 and grid[x][y-1] == 1:\n",
    "                    return -1\n",
    "                elif y== 0 :\n",
    "                    return -1\n",
    "                else:\n",
    "                    return find(x+1, y-1, n, m)\n",
    "            \n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            tmp = find(0, i, n, m)\n",
    "            ans.append(tmp)\n",
    "        \n",
    "        return ans\n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        ans = [-1] * n \n",
    "        Q = deque([])\n",
    "        for i in range(n):\n",
    "            Q.append((0, i, 1, i)) \n",
    "        while Q:\n",
    "            x, y, d, idx = Q.popleft() \n",
    "            if x == m:\n",
    "                ans[idx] = y \n",
    "                continue \n",
    "\n",
    "            if grid[x][y]  == 1:\n",
    "                if d == 1:\n",
    "                    nx, ny, nd = x, y + 1, 0\n",
    "                    if 0<=ny<n and grid[x][ny] == grid[x][y]:\n",
    "                        Q.append((nx,ny,nd, idx))\n",
    "                else:\n",
    "                    nx, ny, nd =  x + 1, y, 1\n",
    "                    Q.append((nx,ny,nd, idx))\n",
    "            else:\n",
    "                if d == 1:\n",
    "                    nx, ny, nd = x, y - 1, 0\n",
    "                    if 0<=ny<n and grid[x][ny] == grid[x][y]:\n",
    "                        Q.append((nx,ny,nd, idx))\n",
    "                else:\n",
    "                    nx, ny, nd =  x + 1, y, 1\n",
    "                    Q.append((nx,ny,nd, idx))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = []\n",
    "\n",
    "        for i in range(n): # 遍历每一个球\n",
    "            up_down_state = True # True: 挡板上方， False: 挡板下方\n",
    "            x = 0 # 球在第几行\n",
    "            y = i # 球在第几列，对应坐标为 (x, y)\n",
    "\n",
    "            while True:\n",
    "                if x == m: # 球已经掉了出来，陷阱：不能判断最后一行，考虑一排队列的情况\n",
    "                    res.append(y)\n",
    "                    break\n",
    "                if grid[x][y] == 1 and up_down_state:\n",
    "                    if y == n-1 or grid[x][y+1] == -1: # 球被卡死\n",
    "                        res.append(-1)\n",
    "                        break\n",
    "                    up_down_state = False\n",
    "                    y += 1\n",
    "                elif grid[x][y] == -1 and up_down_state:\n",
    "                    if y == 0 or grid[x][y-1] == 1:\n",
    "                        res.append(-1)\n",
    "                        break\n",
    "                    up_down_state = False\n",
    "                    y -= 1\n",
    "                else:\n",
    "                    x += 1\n",
    "                    up_down_state = True\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "\n",
    "        def dfs(i, j):\n",
    "\n",
    "            if i < 0 or j >= m or j < 0: return -1\n",
    "            if i == n:return j\n",
    "            curDirec = grid[i][j]\n",
    "            if j + curDirec >= m or j + curDirec < 0 or grid[i][j + curDirec] * grid[i][j] == -1: return -1\n",
    "            else:\n",
    "                return dfs(i + 1, j + curDirec)\n",
    "\n",
    "        res = [ -1] * m\n",
    "\n",
    "        for j in range(m):\n",
    "\n",
    "            res[j] = dfs(0, j)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [-1] * m\n",
    "        \n",
    "        def dfs(row, col):\n",
    "            if row == n:\n",
    "                return col\n",
    "            if grid[row][col] == 1:\n",
    "                if col == m-1 or grid[row][col+1] == -1:\n",
    "                    return -1\n",
    "                return dfs(row+1, col+1)\n",
    "            elif grid[row][col] == -1:\n",
    "                if col == 0 or grid[row][col-1] == 1:\n",
    "                    return -1\n",
    "                return dfs(row+1, col-1)\n",
    "        \n",
    "        for i in range(m):\n",
    "            ans[i] = dfs(0, i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid):\n",
    "\n",
    "        def check(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                if y == n-1:\n",
    "                    return -1\n",
    "                elif grid[x][y+1] == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    y += 1\n",
    "                    x += 1\n",
    "                    if x < m:\n",
    "                        return check(x, y)\n",
    "                    return y\n",
    "            else:\n",
    "                if y == 0:\n",
    "                    return -1\n",
    "                elif grid[x][y-1] == 1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                    x += 1\n",
    "                    if x < m:\n",
    "                        return check(x, y)\n",
    "                    return y\n",
    "        list1 = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(len(grid[0])):\n",
    "            list1.append(check(0, i))\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        #定义一个函数，输入是球所在位置，输出是球落下的位置\n",
    "        def outIndex(x,y):\n",
    "            #如果球在最后一行，直接返回\n",
    "            if x==m:\n",
    "                return y\n",
    "            #如果球不在最后一行，判断其是否可以下落\n",
    "            if y==0 and grid[x][y]==-1:\n",
    "                return -1\n",
    "            if y==n-1 and grid[x][y]==1:\n",
    "                return -1\n",
    "            if grid[x][y]==1:\n",
    "                if grid[x][y+1]==-1:\n",
    "                    return -1\n",
    "            if grid[x][y]==-1:\n",
    "                if grid[x][y-1]==1:\n",
    "                    return -1\n",
    "            \n",
    "            #如果球可以下落，判断下一行的位置\n",
    "            if grid[x][y]==1:\n",
    "                return outIndex(x+1,y+1)\n",
    "            else:\n",
    "                return outIndex(x+1,y-1)\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            res.append(outIndex(0,i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        #假设球当前在[i,j]:\n",
    "        #如果grid[i][j] == 1:\n",
    "            #如果grid[i][j+1] == 1:\n",
    "                #球可以到达[i+1,j+1]\n",
    "            #如果grid[i][j+1] == -1 或者是挡板：\n",
    "                #球卡住\n",
    "        #如果grid[i][j] == -1:\n",
    "            #如果grid[i][j-1] == -1:\n",
    "                #球可以到达[i-1,j-1]\n",
    "            #如果grid[i][j-1] == 1 或者是挡板：\n",
    "                #球卡住\n",
    "        \n",
    "    \n",
    "\n",
    "        #能到达最后一层就通过\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # print(m)\n",
    "        # print(n)\n",
    "        starts = [[0,j] for j in range(n)]\n",
    "        # starts = [[0,0]]\n",
    "        ans = [-1]*n\n",
    "        if n == 1:\n",
    "            return [-1]\n",
    "        cnt = 0\n",
    "        for i,j in starts:\n",
    "            # print(i,j)\n",
    "            # i = x\n",
    "            # j = y\n",
    "            x = i\n",
    "            y = j\n",
    "            # print(\"======\")   \n",
    "            while i >= 0 and i < m and j >= 0 and j < n:\n",
    "                #到底了break\n",
    "                # print(i,j)\n",
    "                if i == m-1:\n",
    "                    if grid[i][j] == 1:\n",
    "                        try:\n",
    "                            if grid[i][j+1] == 1:\n",
    "                                ans[y] = j+1\n",
    "                                cnt += 1\n",
    "                                break\n",
    "                            else:\n",
    "                                ans[y] = -1\n",
    "                                cnt += 1\n",
    "                                break\n",
    "                        except:\n",
    "                            ans[y] = -1\n",
    "                            break\n",
    "                    else:\n",
    "                        try:\n",
    "                            if grid[i][j-1] == -1:\n",
    "                                ans[y] = j-1\n",
    "                                cnt += 1\n",
    "                                break\n",
    "                            else:\n",
    "                                ans[y] = -1\n",
    "                                cnt += 1\n",
    "                                break\n",
    "                        except:\n",
    "                            ans[y] = -1\n",
    "                            break\n",
    "\n",
    "                #没有到底\n",
    "                if grid[i][j] == 1:\n",
    "                    try:\n",
    "                        if grid[i][j+1] == 1:\n",
    "                            i+=1\n",
    "                            j+=1\n",
    "                            # continue\n",
    "                        else:\n",
    "                            ans[y] = -1\n",
    "                            cnt += 1\n",
    "                            break\n",
    "                    except:\n",
    "                        ans[y] = -1\n",
    "                        cnt += 1\n",
    "                        break\n",
    "                elif grid[i][j] == -1:\n",
    "                    try:\n",
    "                        if grid[i][j-1] == -1:\n",
    "                            i+=1\n",
    "                            j-=1\n",
    "                            # continue\n",
    "                        else:\n",
    "                            ans[y] = -1\n",
    "                            cnt += 1\n",
    "                            break\n",
    "                    except:\n",
    "                        ans[y] = -1\n",
    "                        cnt += 1\n",
    "                        break\n",
    "        print(cnt)\n",
    "        print(n)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "                        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid):\n",
    "\n",
    "        def check(x, y):\n",
    "            if grid[x][y] == 1:\n",
    "                if y == n-1:\n",
    "                    return -1\n",
    "                elif grid[x][y+1] == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    y += 1\n",
    "                    x += 1\n",
    "                    if x < m:\n",
    "                        return check(x, y)\n",
    "                    return y\n",
    "            else:\n",
    "                if y == 0:\n",
    "                    return -1\n",
    "                elif grid[x][y-1] == 1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    y -= 1\n",
    "                    x += 1\n",
    "                    if x < m:\n",
    "                        return check(x, y)\n",
    "                    return y\n",
    "        list1 = []\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(len(grid[0])):\n",
    "            list1.append(check(0, i))\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m  = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def getPath(i, j):\n",
    "            if(i == m):\n",
    "                return j\n",
    "            if(grid[i][j] == 1 and j+1 < n and grid[i][j+1] == 1):\n",
    "                return getPath(i+1, j+1)\n",
    "            if(grid[i][j] == -1 and j-1 >= 0 and grid[i][j-1] == -1):\n",
    "                return getPath(i+1, j-1)\n",
    "            return -1\n",
    "        result = []\n",
    "        for j in range(n):\n",
    "            result.append(getPath(0,j))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [-1] * m\n",
    "        \n",
    "        def dfs(row, col):\n",
    "            if row == n:\n",
    "                return col\n",
    "            if grid[row][col] == 1:\n",
    "                if col == m-1 or grid[row][col+1] == -1:\n",
    "                    return -1\n",
    "                return dfs(row+1, col+1)\n",
    "            elif grid[row][col] == -1:\n",
    "                if col == 0 or grid[row][col-1] == 1:\n",
    "                    return -1\n",
    "                return dfs(row+1, col-1)\n",
    "        \n",
    "        for i in range(m):\n",
    "            ans[i] = dfs(0, i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m  = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def getPath(i, j):\n",
    "            if(i == m):\n",
    "                return j\n",
    "            if(grid[i][j] == 1 and j+1 < n and grid[i][j+1] == 1):\n",
    "                return getPath(i+1, j+1)\n",
    "            if(grid[i][j] == -1 and j-1 >= 0 and grid[i][j-1] == -1):\n",
    "                return getPath(i+1, j-1)\n",
    "            return -1\n",
    "        result = []\n",
    "        for j in range(n):\n",
    "            result.append(getPath(0,j))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        def dfs(i, j, state):\n",
    "            \n",
    "            # 到达底部\n",
    "            if i == m - 1 and state == 'down':\n",
    "                return j\n",
    "            \n",
    "            # 在上部分只能往同行同斜线方向的左右移动\n",
    "            if state == 'up':\n",
    "                if 0 <= j + grid[i][j] < n and grid[i][j + grid[i][j]] == grid[i][j]:\n",
    "                    return dfs(i, j + grid[i][j], 'down')\n",
    "                else:\n",
    "                    return -1\n",
    "                \n",
    "            # 在下部分则继续往下行走\n",
    "            else:\n",
    "                if 0 <= i + 1 < m:\n",
    "                    return dfs(i + 1, j, 'up')\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return [dfs(0, k, 'up') for k in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        def dfs(i, j, state):\n",
    "            \n",
    "            # 到达底部\n",
    "            if i == m - 1 and state == 'down':\n",
    "                return j\n",
    "            \n",
    "            # 在上部分只能往同行同斜线方向的左右移动\n",
    "            if state == 'up':\n",
    "                if 0 <= j + grid[i][j] < n and grid[i][j + grid[i][j]] == grid[i][j]:\n",
    "                    return dfs(i, j + grid[i][j], 'down')\n",
    "                else:\n",
    "                    return -1\n",
    "                \n",
    "            # 在下部分则继续往下行走\n",
    "            else:\n",
    "                if 0 <= i + 1 < m:\n",
    "                    return dfs(i + 1, j, 'up')\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return [dfs(0, k, 'up') for k in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m  = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def getPath(i, j):\n",
    "            if(i == m):\n",
    "                return j\n",
    "            if(grid[i][j] == 1 and j+1 < n and grid[i][j+1] == 1):\n",
    "                return getPath(i+1, j+1)\n",
    "            if(grid[i][j] == -1 and j-1 >= 0 and grid[i][j-1] == -1):\n",
    "                return getPath(i+1, j-1)\n",
    "            return -1\n",
    "        result = []\n",
    "        for j in range(n):\n",
    "            result.append(getPath(0,j))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m  = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def getPath(i, j):\n",
    "            if(i == m-1):\n",
    "                if(grid[i][j]==1 and j+1<n and grid[i][j+1]==1):\n",
    "                    return j+1\n",
    "                if(grid[i][j]==-1 and j-1>=0 and grid[i][j-1]==-1):\n",
    "                    return j-1\n",
    "                return -1\n",
    "            if(grid[i][j]==1 and j+1<n and grid[i][j+1]==1):\n",
    "                return getPath(i+1, j+1)\n",
    "            if(grid[i][j]==-1 and j-1>=0 and grid[i][j-1]==-1):\n",
    "                return getPath(i+1, j-1)\n",
    "            return -1\n",
    "        result = []\n",
    "        for j in range(n):\n",
    "            result.append(getPath(0,j))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findBall(self, grid: List[List[int]]) -> List[int]:\n",
    "        m  = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def getPath(i, j):\n",
    "            if(i == m):\n",
    "                # if(grid[i][j]==1 and j+1<n and grid[i][j+1]==1):\n",
    "                #     return j+1\n",
    "                # if(grid[i][j]==-1 and j-1>=0 and grid[i][j-1]==-1):\n",
    "                #     return j-1\n",
    "                return j\n",
    "            if(grid[i][j]==1 and j+1<n and grid[i][j+1]==1):\n",
    "                return getPath(i+1, j+1)\n",
    "            if(grid[i][j]==-1 and j-1>=0 and grid[i][j-1]==-1):\n",
    "                return getPath(i+1, j-1)\n",
    "            return -1\n",
    "        result = []\n",
    "        for j in range(n):\n",
    "            result.append(getPath(0,j))\n",
    "        return result\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
